import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int array[] = {6,1,2,7,9,3,4,5,10,8};
        quickSort(array,0,array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    //快速排序法
    public static void quickSort(int[] array,int left,int right){
        int l = left;
        int r = right;
        //pivot为数组中值
        int pivot = array[(l+r)/2];
        int temp = 0;

        while(l < r){
            //当array[l] < pivot时，左指针右移
            while(array[l] < pivot){
                l++;
            }

            //当array[r] > pivot时，右指针左移
            while(array[r] > pivot){
                r--;
            }

            //当左指针与右指针相遇时，循环结束
            if(l >= r){
                break;
            }

            //左右数列交换位置
            temp = array[r];
            array[r] = array[l];
            array[l] = temp;

            //当array[l] == pivot时，右指针左移
            //直到左右指针相遇
            if(array[l] == pivot){
                r--;
            }

            //当array[r] == pivot时，左指针右移
            //直到左右指针相遇
            if(array[r] == pivot){
                l++;
            }
        }

        //如果 l == r 会出现栈溢出，所以要执行l++和r--
        if(l == r){
            l++;
            r--;
        }

        //左递归
        if(left < r){
            quickSort(array,left,r);
        }

        //右递归
        if(right > l){
            quickSort(array,l,right);
        }
    }
}
